home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_100 / 192_01 / bawkpat.c < prev    next >
Text File  |  1980-01-01  |  8KB  |  369 lines
  1. /*
  2.  * Bawk regular expression compiler/interpreter
  3.  */
  4. #include <stdio.h>
  5. #include "bawk.h"
  6.  
  7. re_compile( patbuf )
  8. char    *patbuf;        /* where to put compiled pattern */
  9. {
  10.     /*
  11.      * Compile a regular expression from current input file
  12.      * into the given pattern buffer.
  13.      */
  14.     int    c,        /* Current character         */
  15.         o;        /* Temp                      */
  16.     char    *patptr,    /* destination string pntr   */
  17.         *lp,        /* Last pattern pointer      */
  18.         *spp,        /* Save beginning of pattern */
  19.         delim,        /* pattern delimiter         */
  20.         *cclass();    /* Compile class routine     */
  21.  
  22.     patptr = patbuf;
  23.     delim = getcharacter();
  24.  
  25.     while ( (c = getcharacter()) != -1 && c != delim )
  26.     {
  27.         /*
  28.          * STAR, PLUS and MINUS are special.
  29.          */
  30.         if (c == '*' || c == '+' || c == '-') {
  31.             if (patptr == patbuf ||
  32.                   (o=patptr[-1]) == BOL ||
  33.                   o == EOL ||
  34.                   o == STAR ||
  35.                   o == PLUS ||
  36.                   o == MINUS)
  37.                 error( "illegal occurrance op", RE_ERROR );
  38.             *patptr++ = ENDPAT;
  39.             *patptr++ = ENDPAT;
  40.             spp = patptr;        /* Save pattern end     */
  41.             while (--patptr > lp)    /* Move pattern down... */
  42.                 *patptr = patptr[-1];    /* one byte     */
  43.             *patptr =   (c == '*') ? STAR :
  44.                 (c == '-') ? MINUS : PLUS;
  45.             patptr = spp;        /* Restore pattern end  */
  46.             continue;
  47.         }
  48.         /*
  49.          * All the rest.
  50.          */
  51.         lp = patptr;            /* Remember start       */
  52.         switch(c) {
  53.  
  54.         case '^':
  55.             *patptr++ = BOL;
  56.             break;
  57.  
  58.         case '$':
  59.             *patptr++ = EOL;
  60.             break;
  61.  
  62.         case '.':
  63.             *patptr++ = ANY;
  64.             break;
  65.  
  66.         case '[':
  67.             patptr = cclass( patptr );
  68.             break;
  69.  
  70.         case ':':
  71.             if ( (c=getcharacter()) != -1 )
  72.             {
  73.                 switch( tolower( c ) )
  74.                 {
  75.  
  76.                 case 'a':
  77.                     *patptr++ = ALPHA;
  78.                     break;
  79.  
  80.                 case 'd':
  81.                     *patptr++ = DIGIT;
  82.                     break;
  83.  
  84.                 case 'n':
  85.                     *patptr++ = NALPHA;
  86.                     break;
  87.  
  88.                 case ' ':
  89.                     *patptr++ = PUNCT;
  90.                     break;
  91.  
  92.                 default:
  93.                     error( "unknown ':' type", RE_ERROR );
  94.  
  95.                 }
  96.             }
  97.             else
  98.                 error( "no ':' type", RE_ERROR );
  99.              break;
  100.  
  101.         case '\\':
  102.             c = getcharacter();
  103.  
  104.         default:
  105.             *patptr++ = CHAR;
  106.             *patptr++ = c;
  107.         }
  108.     }
  109.     *patptr++ = ENDPAT;
  110.     *patptr++ = 0;            /* Terminate string     */
  111.  
  112. #ifdef DEBUG
  113.     if ( Debug>1 )
  114.     {
  115.         for ( lp=patbuf; lp<patptr; ++lp )
  116.         {
  117.             switch ( c = *lp )
  118.             {
  119.             case CHAR:    printf("char "); break;
  120.             case BOL:    printf("bol "); break;
  121.             case EOL:    printf("eol "); break;
  122.             case ANY:    printf("any "); break;
  123.             case CLASS:    printf("class(%d) ", *++lp); break;
  124.             case NCLASS:    printf("notclass(%d) ",*++lp); break;
  125.             case STAR:    printf("star "); break;
  126.             case PLUS:    printf("plus "); break;
  127.             case MINUS:    printf("minus "); break;
  128.             case ALPHA:    printf("alpha "); break;
  129.             case DIGIT:    printf("digit "); break;
  130.             case NALPHA:    printf("notalpha "); break;
  131.             case PUNCT:    printf("punct "); break;
  132.             case RANGE:    printf("range "); break;
  133.             case ENDPAT:    printf("endpat "); break;
  134.             default:    printf("<%c> ", c); break;
  135.             }
  136.         }
  137.         printf( "\n" );
  138.     }
  139. #endif
  140.  
  141.     return patptr - patbuf;
  142. }
  143.  
  144. char *
  145. cclass( patbuf )
  146. char    *patbuf;    /* destination pattern buffer */
  147. {
  148.     /*
  149.      * Compile a class (within [])
  150.      */
  151.     char    *patptr,    /* destination pattern pointer */
  152.         *cp;        /* Pattern start     */
  153.     int    c,        /* Current character */
  154.         o;        /* Temp              */
  155.  
  156.     patptr = patbuf;
  157.  
  158.     if ( (c = getcharacter()) == -1 )
  159.         error( "class terminates badly", RE_ERROR );
  160.     else if ( c == '^')
  161.     {
  162.         /*
  163.          * Class exclusion, for example: [^abc]
  164.          * Swallow the "^" and set token type to class exclusion.
  165.          */
  166.         o = NCLASS;
  167.     }
  168.     else
  169.     {
  170.         /*
  171.          * Normal class, for example: [abc]
  172.          * push back the character and set token type to class
  173.          */
  174.         ungetcharacter( c );
  175.         o = CLASS;
  176.     }
  177.     *patptr++ = o;
  178.  
  179.     cp = patptr;    /* remember where byte count is */
  180.     *patptr++ = 0;    /* and initialize byte count */
  181.     while ( (c = getcharacter()) != -1 && c!=']' )
  182.     {
  183.         o = getcharacter();        /* peek at next char */
  184.         if (c == '\\')            /* Store quoted chars */
  185.         {
  186.             if ( o == -1) /* Gotta get something */
  187.                 error( "class terminates badly", RE_ERROR );
  188.             *patptr++ = o;
  189.         }
  190.         else if ( c=='-' && (patptr-cp)>1 && o!=']' && o != -1 )
  191.         {
  192.             c = patptr[-1];        /* Range start     */
  193.             patptr[-1] = RANGE;    /* Range signal    */
  194.             *patptr++ = c;        /* Re-store start  */
  195.             *patptr++ = o;        /* Store end char  */
  196.         }
  197.         else
  198.         {
  199.             *patptr++ = c;        /* Store normal char */
  200.             ungetcharacter( o );
  201.         }
  202.     }
  203.     if (c != ']')
  204.         error( "unterminated class", RE_ERROR );
  205.     if ( (c = (patptr - cp)) >= 256 )
  206.         error( "class too large", RE_ERROR );
  207.     if ( c == 0 )
  208.         error( "empty class", RE_ERROR );
  209.     *cp = c;        /* fill in byte count */
  210.  
  211.     return patptr;
  212. }
  213.  
  214. match( line, pattern )
  215. char    *line;        /* line to match */
  216. char    *pattern;    /* pattern to match */
  217. {
  218.     /*
  219.      * Match the current line (in Linebuf[]), return 1 if it does.
  220.      */
  221.     char    *l;        /* Line pointer       */
  222.     char    *pmatch();
  223.     char    *next;
  224.     int    matches;
  225.  
  226.     matches = 0;
  227.     for (l = line; *l; l++)
  228.     {
  229.         if ( next = pmatch(line, l, pattern) )
  230.         {
  231.             l = next - 1;
  232.             ++matches;
  233. #ifdef DEBUG
  234.             if ( Debug )
  235.                 printf( "match!\n" );
  236. #endif
  237.         }
  238.     }
  239.  
  240.     return matches;
  241. }
  242.  
  243. char *
  244. pmatch(linestart, line, pattern)
  245. char    *linestart;    /* start of line to match */
  246. char    *line;        /* (partial) line to match      */
  247. char    *pattern;    /* (partial) pattern to match   */
  248. {
  249.     char    *l;    /* Current line pointer         */
  250.     char    *p;    /* Current pattern pointer      */
  251.     char    c;    /* Current character            */
  252.     char    *e;    /* End for STAR and PLUS match  */
  253.     int    op;    /* Pattern operation            */
  254.     int    n;    /* Class counter                */
  255.     char    *are;    /* Start of STAR match          */
  256.  
  257.     l = line;
  258.  
  259. #ifdef DEBUG
  260.     if (Debug > 1)
  261.         printf("pmatch(\"%s\")\n", line);
  262. #endif
  263.  
  264.     p = pattern;
  265.     while ((op = *p++) != ENDPAT) {
  266.  
  267. #ifdef DEBUG
  268.         if (Debug > 1)
  269.             printf("byte[%d] = 0%o, '%c', op = 0%o\n",
  270.                     l-line, *l, *l, op);
  271. #endif
  272.  
  273.         switch(op) {
  274.  
  275.         case CHAR:
  276.             if ( *l++ != *p++)
  277.                 return 0;
  278.             break;
  279.  
  280.         case BOL:
  281.             if (l != linestart)
  282.                 return 0;
  283.             break;
  284.  
  285.         case EOL:
  286.             if (*l != '\0')
  287.                 return 0;
  288.             break;
  289.  
  290.         case ANY:
  291.             if (*l++ == '\0')
  292.                 return 0;
  293.             break;
  294.  
  295.         case DIGIT:
  296.             if ((c = *l++) < '0' || (c > '9'))
  297.                 return 0;
  298.             break;
  299.  
  300.         case ALPHA:
  301.             c = tolower( *l++ );
  302.             if (c < 'a' || c > 'z')
  303.                 return 0;
  304.             break;
  305.  
  306.         case NALPHA:
  307.             c = tolower(*l++);
  308.             if (c >= 'a' && c <= 'z')
  309.                 break;
  310.             else if (c < '0' || c > '9')
  311.                 return 0;
  312.             break;
  313.  
  314.         case PUNCT:
  315.             c = *l++;
  316.             if (c == 0 || c > ' ')
  317.                 return 0;
  318.             break;
  319.  
  320.         case CLASS:
  321.         case NCLASS:
  322.             c = *l++;
  323.             n = *p++ & 0377;
  324.             do {
  325.                 if (*p == RANGE) {
  326.                     p += 3;
  327.                     n -= 2;
  328.                     if (c >= p[-2] && c <= p[-1])
  329.                         break;
  330.                 }
  331.                 else if (c == *p++)
  332.                     break;
  333.             } while (--n > 1);
  334.             if ((op == CLASS) == (n <= 1))
  335.                 return 0;
  336.             if (op == CLASS)
  337.                 p += n - 2;
  338.             break;
  339.  
  340.         case MINUS:
  341.             e = pmatch(linestart,l,p);/* Look for a match    */
  342.             while (*p++ != ENDPAT);    /* Skip over pattern   */
  343.             if (e)            /* Got a match?        */
  344.                 l = e;        /* Yes, update string  */
  345.             break;            /* Always succeeds     */
  346.  
  347.         case PLUS:            /* One or more ...     */
  348.             if ((l = pmatch(linestart,l,p)) == 0)
  349.                 return 0;    /* Gotta have a match  */
  350.         case STAR:            /* Zero or more ...    */
  351.             are = l;        /* Remember line start */
  352.             while (*l && (e = pmatch(linestart,l,p)))
  353.                 l = e;        /* Get longest match   */
  354.             while (*p++ != ENDPAT);    /* Skip over pattern   */
  355.             while (l >= are) {    /* Try to match rest   */
  356.                 if (e = pmatch(linestart,l,p))
  357.                     return e;
  358.                 --l;        /* Nope, try earlier   */
  359.             }
  360.             return 0;        /* Nothing else worked */
  361.  
  362.         default:
  363.             fprintf( stderr, "bad op code %d\n", op );
  364.             error( "can't happen -- match", RE_ERROR );
  365.         }
  366.     }
  367.     return l;
  368. }
  369.